1. Field of Invention
The present invention relates to content addressable memory (CAM), and more specifically content addressable memory storage elements suitable for constructing high-speed, large-capacity, binary or ternary CAM arrays.
2. Description of the Background Art
A content addressable memory (CAM) is a memory in which a group of memory elements are selected or identified by their content, rather than by their physical location. A CAM includes a matrix of CAM cells arranged in rows and columns. Each CAM cell includes compare logic, and stores one bit of digital information. One or more bits of information constitute a word. A content addressable memory compares a search word (comparand) with a set of words stored within the CAM. During the compare operation, an indicator associated with each stored word produces a comparison result, indicating whether or not the search word matches the stored word.
FIG. 1 shows one particular binary CAM cell according to prior art, including a match logic circuit (transistors T2, T3 and T4), two transistor access devices T0 and T1, and a memory element D0. The memory element D0 stores one bit of digital information. FIG. 2 shows a typical implementation of a static memory element D0 using two NMOS transistors T2 and T3 and two PMOS transistors T0 and T1, according to prior art. The static memory element D0 has two states and two complementary cell nodes C and CN. In one state, C has a high signal level and CN has a low signal level, whereas in the other state, CN has a high level and C has a low level. The two access devices T0 and T1 in FIG. 1 couple the memory element D0 to two complementary bit lines BL and BLN, respectively. The data access device T0 connects C to BL and the second access device T1 connects CN to BLN. A word line WL connects together the gate terminals of the two access devices T0 and T1. A comparator having two transistor discharge devices T3 and T2 couples the two cell nodes C and CN respectively to two complementary compare lines designated as K and KN. The output of the comparator, designated as X, indicates the result of the comparison. The comparison results for an entire word in a binary CAM array are transmitted to a match line ML via the match output device T4 in a wired-NOR configuration.
A binary CAM cell has three distinct modes of access by means of the following operations; a read operation, a write operation and a compare operation.
1) During the read operation, the signal level at WL (initially low) is asserted high, activating the two access devices T0 and T1. With WL high, the activated data access device T0 is conducting, and C is electrically connected to BL. Similarly, when WL is high, an electrical connection is made between CN and BLN via the second access device T1. Once such electrical connection is established, the one bit of differential data stored in the memory element D0 of the CAM cell is transmitted or read out to the bit lines BL and BLN. After a read operation, WL is returned low, de-activating the two access devices T0 and T1, and thereby isolating the memory element D0 from the bit lines. Bit lines BL and BLN (initially precharged to a high state) are returned to a precharged (reset) state following the read operation. FIG. 3 shows the signal levels and timing for a typical read operation, according to prior art. PA0 2) During the write operation, one bit of differential data is placed on the bit lines BL and BLN. One state is asserted on BL and its complement is placed on BLN. WL (initially low) is asserted high, activating the two access devices T0 and T1. With WL high, the activated data access device T0 is conducting, and C is electrically connected to BL. Similarly, an electrical connection is made between CN and BLN via the second access device T1. The differential data placed on the bit lines BL and BLN, is transmitted or written to the memory element D0 of the CAM cell for storage. Upon completion of a write operation, WL is returned low, de-activating transistors T0 and T1, and thereby isolating the memory element D0 from the bit lines. Bit lines BL and BLN (initially precharged to high state) are returned to the precharged (reset) state following the write operation. FIG. 4 shows the signal levels and timing for the write operation. PA0 3) For the compare operation, one bit of differential compare data is placed on the compare lines K and KN. One state is asserted on K while its complement is placed on KN. The comparator logic circuit determines if the bit of compare data is equivalent to the data stored in the memory element D0. If K is equivalent to C in signal level, then the comparator output node X is low and the match line ML (initially precharged high) remains unaffected--indicating a match. If K is not equivalent to C, then the comparator output node X goes high to enable T4, and ML is pulled low--indicating a non-match (also called a "miss"). For example, if both C and KN are high then an output node X of the comparator is charged high through T3, activating the match output device T4. Consequently, the wired-NOR match output at ML is pulled low by T4, indicating a non-match. Similarly, if CN and K are both high then the output node X is charged high through T2, activating the pull down device T4. Subsequently, ML is pulled low indicating a non-match. After a compare operation, both compare lines K and KN are returned to a low signal level to discharge the comparator output node X through either T2 or T3 depending on the state of the memory element D0. Discharging of the output node X resets the comparator discharge devices T2 and T3, disables T4 and allows ML to be precharged to a high state for the next compare operation. FIG. 5 shows typical signal levels and timing for the compare operation, according to prior art. PA0 1) The compare lines are typically connected to the source or drain terminals of the comparator circuit transistors, causing the compare lines to be heavily loaded resulting in higher power consumption, and slower search operations. It should also be noted that for a CAM cell similar to FIG. 1, the loading on the compare lines is data dependant, which means that the CAM must be designed for memory data patterns which represent the worst case loading conditions. For example, if all CAM cells in the same column of the CAM array contain the same data, a non-match within the column would require one compare line to discharge all the X nodes within the column. The result is an increased effective load on one of the compare lines. PA0 2) The comparator output node X does not experience a full signal swing. The discharge devices T2 or T3 are unable to charge the output node X to a voltage equivalent to the full power supply voltage. As a result, the match output device T4 is not completely turned on and the discharge of the match line ML is done at a slower rate, thereby slowing down the matching process. One could employ PMOS devices for the comparator to solve this problem, however in doing so another problem is created. PMOS devices would not be able to discharge the output node X completely, making the resetting of ML difficult if not impossible, since NMOS match output transistor T4 would remain on. PA0 3) The use of wired-NOR matching is also unfavourable due to excessive power dissipation in the match lines. In wired-NOR matching, ML is discharged for non-matches. In applications where the majority of words are expected to mis-match, this technique is overly inefficient. Another disadvantage of using wired-NOR matching is that the rate of discharge of ML depends on how many CAM cells in a word are non-matching. The peak power demands of each mis-matched word is data dependant and the array must be designed according to memory patterns representing the worst case conditions. PA0 (1) Bit lines are separated from the compare lines to reduce loading on both the compare lines and bit lines, permitting the construction of larger and faster CAM arrays. With separate compare and bit lines, the search operation can be performed without affecting precharge timing of the read/write operation. Furthermore, signal levels of the compare lines at the end of search operation do not have to coincide with precharge levels for a read/write operation. The result is a CAM cell with a bandwidth potential approaching twice that of a CAM cell without separate bit and compare lines. PA0 (2) Local amplification for the compare lines is provided through the gates of discharge devices. This way, loading on the compare lines is independent of data stored in the CAM cells. In addition, loading on the compare lines is reduced, since the compare lines are connected to the gate terminals of the comparator means rather than to the source or drain terminals. PA0 (3) Means for precharging the comparator output is provided, which generates full swing logic levels and functions as a reset of the comparator after a compare operation. Full swing logic levels at the comparator output provide faster matching for wired-NOR or NAND matching. PA0 (4) In the case of a ternary CAM cell, means for disabling the comparator are provided, thereby allowing one bit to represent the mask and the other bit to represent the data, without a requirement for special encoding of the mask and data. In this configuration, the mask and data information may be read and written from the storage cells separately and independently of one another. This way, data information is not lost and may be retrieved with a normal read data operation. Furthermore, the mask and data bits may be read and written at different times independently of one another. PA0 In an embodiment of this invention, the content addressable memory cell further comprises match means responsive to the comparator output, wherein said content addressable memory cell is a member of a plurality of similarly formed content addressable memory cells accessing a match line driven by respective said match means of each of the content addressable memory cells. Preferably, the match means for each one of the plurality of similar content addressable memory cells comprises a logic NAND device positioned in series with one another along the match line. Alternatively, the match means for each one of the plurality of similar content addressable memory cells comprises a logic NOR device positioned in parallel with one another between a power supply node and the match line. PA0 The memory element can contain a static memory device, a dynamic memory device, a non-volatile memory device, or a single-ended memory device. PA0 A) The access means comprises transistor means responsive to the word line for coupling the cell node to the bit line. PA0 B) The comparator means comprises a pair of a first and a second transistor means in a series configuration for coupling the cell node to a power supply node, wherein said first transistor means is responsive to the compare line and said second transistor means is responsive to the cell node. PA0 C) The resetting means comprises transistor means responsive either to the compare line for coupling the comparator output to a power supply node, or to a precharge line for coupling the comparator output to a power supply node. PA0 In another embodiment of this invention, the content addressable memory cell further comprises match means responsive to the comparator output, wherein said content addressable memory cell is a member of a plurality of similarly formed content addressable memory cells accessing a match line driven by respective said match means of each of the content addressable memory cells. PA0 A) The comparator means comprises transistor means responsive to the compare line for coupling the data cell node to the comparator output, and the disable means comprises transistor means responsive to a complement of the compare line for coupling the mask cell node to the comparator output. PA0 B) The disable means comprises transistor means for either decoupling the data cell node from the comparator means, shunting the comparator means, or shunting the logic NAND device when implemented within the match line.
There are several known approaches to CAM cells in the art. A journal paper by Kenneth J. Schultz entitled "A Survey of Content-addressable Memory Cells" published in Integration, the VLSI Journal, Vol. 23, pp. 171-188, 1997 describes several CAM cell designs and summarizes the advantages and disadvantages of each. The CAM cell of FIG. 1 and other similar configurations in the art, have certain unfavourable characteristics for constructing high-performance, large-capacity CAM arrays such as the following:
A dynamic-NAND match function is one approach known in the art for reducing match line power dissipation in CAM's. European Patent Application, #98300490.4 published on Aug. 12, 1998 and corresponding U.S. Pat. No. 5,859,791 show a means for a dynamic NAND match in CAM's. A CAM cell employing a dynamic-NAND match reduces the power dissipation in CAM arrays permitting the construction of high-performance, large-capacity arrays. A journal paper by Kenneth J. Schultz entitled "25 MHz Fully-Parallel Content Addressable Memory", published in the Journal of Solid States Circuits, Vol. 23, pp 1690-1696, November 1998, shows how a dynamic NAND match reduces power dissipation in CAM's and gives evidence that high-performance, large-capacity CAM arrays are realizable with this technique.
In view of the above discussion of prior art, there is clearly a need for CAM cell configurations that demand relatively lower power consumption while offering a relatively faster match and search operation.
It is known in the art, that a column of CAM cells may be excluded from the search or compare operation by asserting both compare lines low (or high in some CAM cells). This however, does not provide masking on a per cell basis. In order to exclude particular CAM cells from a search or compare, an additional storage bit is required to represent more than two states. A third state representing a "don't care" or "masked" state may be used to exclude the CAM cell from the search or compare operation, by forcing the cell to match regardless of the applied comparand data, K and KN. Cells capable of storing a third state for per bit masking purposes are known in the art as ternary CAM cells.
In regards to a ternary CAM configuration, U.S. Pat. Nos. 5,319,590 and 5,051,949 disclose the use of two storage bits and a compare logic circuit per CAM cell to encode a "don't care" state. A "don't care" state excludes the CAM cell from comparison by forcing the CAM cell to match independent of the state of the inputs at the compare lines K and KN. The ternary CAM cell designs described in these two patents store data and mask information in an encoded format. A problem with this approach is that during decoding, the masked data information is lost where masked data is read out as "0" or low state. Encoding also requires that both mask and data be written simultaneously. In this respect it is desirable to have a new CAM design that avoids the need for encoding the information.